package com.github.hgkmail.hello.leetcode101.sort;

import com.github.hgkmail.hello.leetcode101.base.CommonUtil;

import java.util.Arrays;

/**
 * 总结：
 * 1.左闭右开的写法，不要取等号
 * 2.right-- 要在 left++ 前面，不然结果不正确
 * 3.swap -> partition -> quicksort递归
 */
public class Quicksort {

    //快排应该使用左闭右开，因为里面的大小关系都是不能取等号的，这与左闭右开一致
    public int partition(int[] nums, int l, int r) {
        //选第一个元素当哨兵
        int key=nums[l];
        int i=l;
        int j=r-1;
        //下面的 i<j 都不能有等号
        while (i<j) {
            //不知道为啥，j--必须排在前面，不然结果不正确！
            while (i<j && nums[j]>=key) {
                j--;
            }
            while (i<j && nums[i]<=key) {
                i++;
            }
            if (i<j) {
                CommonUtil.swap(nums, i, j);
            }
        }
        CommonUtil.swap(nums, l, i);
        return i;
    }

    public void quicksort(int[] nums, int l, int r) {
        if (l+1>=r) { //只有一个元素，比如[0,1)，不用排序
            return;
        }
        int pivot = partition(nums, l, r); //左边都小于等于pivot，右边都大于等于pivot
        quicksort(nums, l, pivot);
        quicksort(nums, pivot+1, r);
    }

    public static void main(String[] args) {
        int[] nums=new int[]{1, 8, 2, 7, 100, 5, 9, 0};
        new Quicksort().quicksort(nums, 0, nums.length);
        System.out.println(Arrays.toString(nums));
    }
}
